1. Field of the Invention
The present invention relates to a distribution generation system for generating a stochastic measure on a finite set. Furthermore, the present invention relates to an optimization system, which applies the distribution generation system to search an optimized value of a physical quantity determined by one or a plurality of parameters.
2. Description of the Related Art
Application of a system for searching a minimum value of a function having discrete or continuous domains in a domain of definition to various fields has been examined. For this purpose, extensive studies and developments have been made.
As the above-mentioned system, an optimization system for searching an optimized value of a physical quantity determined by one or a plurality of parameters is known.
For example, the optimization system is utilized in a field to be described below.
(a) Core Design of Power Generation Nuclear Reactor
Assume that the core has a cylindrical shape having a radius of r m and a height of h m, and the degree of enrichment of a fuel stored in the core is represented by uk g/m.sup.3. In order to continue an operation, the following critical condition must be established: ##EQU1## where .alpha. and k are constants.
On the other hand, cost necessary for constructing the above-mentioned core is approximately given by: where a.sub.1, a.sub.2, and a.sub.3 are constants. EQU c(r,h,u)a.sub.1 r.sup.2 hu+a.sub.2 .sqroot.v-a.sub.3 r.sqroot.h
In order to optimally design the core according to the above-mentioned conditions, the following optimization problem must be solved. ##EQU2## where r.sub.m, h.sub.m, and u.sub.m are constants. (b) LSI Layout
In order to efficiently utilize a wafer by increasing the degree of integration of LSIs, each LSI must be laid out to minimize the circuit area. As one solution to the problem, the following method is known.
The antecedent conditions for this layout are set as follows:
(1) An area S where a circuit is assumed to be laid out is given in advance. PA1 (2) A circuit is considered as a graph having connecting lines among units. PA1 (3) Each unit is assumed to have a predetermined area. PA1 (4) Units are classified into two groups, and are laid out to minimize the number of connecting lines extending between the two groups. PA1 (5) The total sum of the areas of units in each group is set not to exceed an area where the units in the group are to be laid out, i.e., S/2 in this case. PA1 (1) A load is only an axial compression force, and the girder is supported at two ends. PA1 (2) The girder is designed under a condition disregarding elastic buckling and plastic buckling for overall buckling of the girder as a column, and local buckling of plates constituting the girder. PA1 (3) The optimal sectional shape is one corresponding to the minimum girder weight. That is, the sectional shape having a minimum volume is obtained under an assumption that a uniform material is used. PA1 (4) The box girder is assumed to have a square section, and parameters representing the sectional shape are represented by a plate thickness t and a plate width a. PA1 (1) When a smooth nonlinear function defined by a continuous domain is solved without any restriction conditions, the system is operated in the steepest descent method. PA1 (2) When a quadratic function having discrete domains of definition is optimized, the simulated annealing method is often used.
The above-mentioned conditions are applied to the two equally divided groups, thereby obtaining a schematic LSI layout.
In this method, the schematic layout is obtained by solving the following optimization problem when the units are equally divided into the two groups for the first time. The total number of units is represented by n, and the units are numbered from 1 to n. The number of connecting lines between units j and k is represented by c.sub.jk (for c.sub.jk =c.sub.kj) An area occupied by the unit j is represented by oj. ##EQU3## (c) Box Girder Design
In the box girder design, the sectional shape of a box girder, which receives a uniform axial pressure, is designed when the magnitude of an axial compression force and the length of the girder are given.
In this case, conditions are as follows.
The box girder can be optimally designed by finding out parameters that satisfy the following conditions of the parameters t and a for minimizing a volume V=AL under the above-mentioned assumptions: EQU Conditions n.sigma..ltoreq..sigma..sub.c * and n.sigma..ltoreq..sigma.p*
In this case, when A=4at. I=(2/3)a.sup.3 t, and .sigma.=P/A. we have: ##EQU4## where P is the axial compression force, L is the length of the girder, E is the Young's modulus, .nu. is the Poisson ratio, .sigma.y is the yield point, and n is the safety factor for buckling.
The above-described optimization system is utilized in combination with a physical quantity computer. For example, in the case (c), the optimization system supplies the values of the parameters t and a to the physical quantity computer. The physical quantity computer calculates the volume V on the basis of the values of the parameters t and a, and sends back the volume V to the optimization system. The optimization system changes the values of the parameters t and a on the basis of the volume V, and sends the parameters to the physical quantity computer again. After the abovementioned process is repeated a finite number of times, the optimization system outputs a plate thickness t and a plate width a, which can minimize the volume V.
There are many problems of minimizing (or maximizing) a target function under given limitation conditions over various industrial fields in addition to the above-mentioned cases. As a means for solving these problems, an optimization searching technique is widely utilized.
An optimization system of this type is executed by classifying given problems according to the natures of minimized functions (to be referred to as target functions) or restriction conditions, and selecting different operations. For example,
In addition to the above methods, the random method may be used.
The steepest descent method is a method of searching an optimized solution by repeating a small movement in a direction to minimize a function value from one point on the domain of definition as a start point. The direction to minimize a function value is determined by partially differentiating a function. More specifically, a movement is performed in a direction opposite to the gradient of the function (i.e., the sign inverting direction of a vector). FIG. 1 shows a state wherein the optimized solution is searched by repeating a small movement in a direction to decrease a function value.
The simulated annealing method is a kind of the Monte Carlo method. Assume that there are a corollary S consisting of N units each assuming two values (e.g., .+-.1), and a quadratic function V defined as follows for possible conditions s of the corollary S. ##EQU5##
In this case, the object is to obtain a condition for minimizing V. For this purpose, the following procedure is executed. Assuming that the corollary is in a condition s.sub.1, one of spins is selected, and a condition wherein the sign of the selected spin is inverted is represented by s.sub.2. A value V(s.sub.2)-V(s.sub.1) is calculated. If the calculation result is negative, the sign of the spin is inverted, and the corollary is set in the condition s.sub.2. Otherwise, the sign of the spin is inverted at a probability of exp(-.beta.(V(s.sub.1)-V(s.sub.2))) (where .beta. is a positive constant).
A probabilistic transition is repeated by changing a spin to be selected, as described above. In this case, all the spins are uniformly selected. As the probabilistic transition is repeated, the value .beta. is gradually increased. At this time, the rate of increase in .beta. must be very slow (normally, the order of the logarithm is eliminated). As a result, after an elapse of a predetermined period of time, the corollary can obtain a condition for minimizing V.
The random method is a method of searching a point for minimizing a function value by repeating an operation for uniformly selecting a point on the domain of definition, and determining a function value at the selected point.
According to the conventional optimization system, an application range is limited depending on the natures of target functions and restriction conditions, resulting in poor versatility. Even when a target function defined by a continuous domain is to be optimized, a global minimum value cannot always be searched (obtained). In fact, an optimized solution can be obtained by, e.g., the steepest descent method only when a function does not have a plurality of minimal values in a domain to be searched. Although an operation according to the random method can search a global minimum value, its searching efficiency is very poor. The simulated annealing method can search a global minimum value, and can improve searching efficiency as compared to the random method. However, since parallel processing that can be executed in the random method cannot be executed in this method, searching efficiency is also poor. This method is effective for only a target function having discrete domains of definition.
The distribution generation system is used for the following purpose.
In order to simulate or test a computer system, jobs must be generated according to a specific distribution (probability distribution) such as a normal distribution, Poisson distribution, and the like. The distribution generation system is used for generating events according to the probability distribution. The distribution generation system is utilized not only in a computer system but also in a system for generating a dummy accident so as to verify the reliability of a technologically designed system. Random numbers are often used upon constitution of a system. The random number generation system is also a distribution generation system for uniformly generating probability events according to a distribution.
When random variables having a specific distribution on a bounded period are constituted, the conventional distribution generation system employs a method of modifying a uniform distribution obtained by uniformly random numbers by a function. For example, when f is a function for transferring a period [0, 1] to the period [0, 1], f(r) represents random variables according to a specific distribution on [0, 1] with respect to random numbers r uniformly distributed on the period [0, 1]. The function f can be properly determined according to a required distribution form. This method is used upon constitution of random variables taking a finite number of values, and complying with an arbitrarily given distribution. For example, in order to constitute random variables respectively taking values 1, 2, and 3 at probabilities of 1/2, 1/3, and 1/4, the following function can be adopted as the abovementioned f. ##EQU6##
According to the conventional distribution generation system, it is generally difficult to constitute random variables, which assume values in a multidimensional space, and comply with an arbitrarily given distribution. When random variables taking a finite number of values are to be constituted, it is practically impossible to obtain a function used in modification of random numbers when the number of values is huge.
The associated techniques of the present invention are disclosed in A. Corona et al.,; "Minimizing Multimodel Functions of Continuous Variables with the "Simulated Annealing" algorithm", ACM Trans. Math. Software, Vol. 13, No. 3, Sep. 1987, pp. 262-280, and "Simulated Annealing; Theory and Applications", P. J. M. Laarhoven and E. H. L. Aarts; Reidel, 1987, pp. 148-152.